Programs executed by computers and other processor based devices typically exhibit repetitive patterns. It has long been know that identifying such repetitive patterns provides an opportunity to optimize program execution. For example, software and firmware programmers have long taken advantage of small scale repetitive patterns through the use of iterative loops, etc. to reduce code size, control memory allocation and perform other tasks seeking to optimize and streamline program execution.
Recently, there has been increased interest in seeking to identify larger scale repetition patterns in complicated workloads such as, for example, managed run-time environments and other server-based applications as a mechanism to optimize handling of those workloads. For instance, it is known that a workload may be conceptualized as a series of macroscopic transactions. As used herein, the terms macroscopic transaction and sub-transaction refer to a business level transaction and/or an application software level transaction. For instance, the workload of a server at an Internet retailer such as Amazon.com may be conceptualized as an on-going sequence of macroscopic transactions and sub-transactions such as product display, order entry, order processing, customer registration, payment processing, etc. Moving to a more microscopic level, each of the macroscopic transactions in the workload may be seen as a series of program states. It is desirable to optimize the execution of workloads by, for example, reducing the time it takes the hosting computer to transition between and/or execute macroscopic transactions and/or program states. Therefore, there is an interest in identifying repetition patterns of program states in macroscopic transactions in the hope of predicting program state transitions, optimizing the execution of macroscopic transactions and/or program states, and increasing the throughput of the workload associated with such transactions.
There have been attempts to exploit repetitive structures such as loops to, for example, prefetch data to a cache. However, those prior art methodologies have been largely limited to highly regular and simple workloads such as execution of scientific codes. Effectively predicting program states and/or macroscopic transactions for larger, more complicated workloads remains an open problem.